#include<iostream>
#include<iomanip>
#include<string>
#include<sstream>
#include<vector>
#include<list>
#include<utility>
#include<cstring>
#include<cstdio>

#include "Util.h"
using namespace std;

struct TreeNode
{
	struct TreeNode * left;
	struct TreeNode * right;
    int value;
    int balance;
};

//下面是从AVL中拷贝过来的函数，为了方便验证splay过程是正确的用
//旋转函数
struct TreeNode *Rotate(struct TreeNode *root, struct TreeNode *child);
//辅助旋转函数
struct TreeNode *TurnLeft(struct TreeNode *root, struct TreeNode *child);
struct TreeNode *TurnRight(struct TreeNode *root, struct TreeNode *child);
//插入函数
struct TreeNode *Insert(int value, struct TreeNode *root, bool& is_taller);


//如果指定value节点存在的话，则该节点会成为root，如果value节点不存在的话
//则新增一节点，使它拥有value值，并成为root
struct TreeNode * SplayInsert(int value, struct TreeNode *root);
//与上面SplayInsert的区别就在于，该函数只进行Splay动作，而不会进入节点的增加
struct TreeNode * Splay(int value, struct TreeNode *root);

/*
//打印root的树情况
void Display(const string& msg, struct TreeNode *root);
*/


int main()
{
    bool flag=false;
    struct TreeNode *root=Insert(8,NULL,flag);
    root=Insert(5,root,flag);
    root=Insert(12,root,flag);
    root=Insert(3,root,flag);
    root=Insert(6,root,flag);
    root=Insert(10,root,flag);
    root=Insert(13,root,flag);
    Display("vm_page_splay Insert",root);

    bool myflag=false;
    struct TreeNode* myroot=Insert(8,NULL,myflag);
    myroot=Insert(5,myroot,myflag);
    myroot=Insert(12,myroot,myflag);
    myroot=Insert(3,myroot,myflag);
    myroot=Insert(6,myroot,myflag);
    myroot=Insert(10,myroot,myflag);
    myroot=Insert(13,myroot,myflag);
    Display("mysplay insert",myroot);


    myroot=Splay(5,myroot);
    Display("mysplay 5",myroot);
    getchar();

    myroot=Splay(12,myroot);
    Display("mysplay 12",myroot);
    getchar();

    myroot=Splay(10,myroot);
    Display("mysplay 10",myroot);
    getchar();

    myroot=Splay(13,myroot);
    Display("mysplay 13",myroot);
    getchar();

    myroot=Splay(6,myroot);
    Display("mysplay 6",myroot);
    getchar();

    myroot=Splay(8,myroot);
    Display("mysplay 8",myroot);
    getchar();

}

//
//Splay Tree可以分成三部分
//           root
//          /    \
//         /      \
//      left      right
// 左子树中的最右边的节点是左子树中最大的节点，用leftMax来表示这个节点
// 右子树中的最左边的节点是右子树中最小的节点，用rightMin来表示这个节点
//
// 而整个Splay的过程中，其实就是根据要Splay的值来重新构成一棵树,不断地和
// value做比较，比value小的节点保存到leftMax->right中（因为左子树比root节点
// 小，root要保存到左子树的话，只能保存在RightMost节点的right指针中）;比
// value大的节点保存到rightMin->left中（右子树比root节点大，root节点只能
// 保存到右子树的LeftMost节点的left指针中）
//
// 如果指定的value节点存在于当前树中，会进行splay动作，如果指定的value节点
// 不存在于当前树中，则自动插入该节点，同时该节点成为root
struct TreeNode * SplayInsert(int value, struct TreeNode *root)
{
    struct TreeNode target;
    target.left=target.right=NULL;

    //leftMax和rightMin用来重构左右子树
    struct TreeNode *leftMax=&target;
    struct TreeNode *rightMin=&target;
    struct TreeNode *tmp=NULL;

    while(root!=NULL)
    {
        if(root->value<value)
        {
            tmp=root->right;
            //这种情况需要旋转,和AVL中的"Right Right Case"旋转相同
            if(tmp!=NULL && tmp->value<value)
            {
                root->right=tmp->left;
                tmp->left=root;
                root=tmp;
            }
            //root节点比value小，把root节点记录到leftMax中
            leftMax->right=root;
            leftMax=root;
            //旋转后value依然比root节点的值大
            //      root                             node1
            //          \                            /   \
            //           node1      旋转==>        root  node3
            //           /   \                     /
            //        node2   node3              node2
            //
            root=root->right;

        }else if(root->value>value)
        {
            tmp=root->left;
            //这种情况同样需要旋转，与AVL中的"Left Left Case"旋转相同
            if(tmp!=NULL && tmp->value>value)
            {
                root->left=tmp->right;
                tmp->right=root;
                root=tmp;
            }
            //root节点比value大，记录到rightMin中
            rightMin->left=root;
            rightMin=root;
            //旋转后的value比root节点的值小
            //         root                       node1
            //         /                          /    \
            //     node1            旋转==>   node2    root  
            //     /   \                                 \
            //  node2 node3                             node3
            root=root->left;
        }
        //找到节点
        else
        {
            //切换当前节点的左右子树的关联，把左子树保存到leftMax中
            //右子树保存到rightMax中
            leftMax->right=root->left;
            rightMin->left=root->right;
            break;
        }
    }

    //这种情况是当前树中没有要找的节点，此时新插入一个节点
    if(root==NULL)
    {
        leftMax->right=NULL;
        rightMin->left=NULL;
        root=new TreeNode;
        root->value=value;
    }

    //连接左右子树，此时整个树的重构完成
    root->left=target.right;
    root->right=target.left;

    return root;
}

//Splay函数只进行Splay动作而不进行新节点的增加
struct TreeNode * Splay(int value, struct TreeNode *root)
{
    struct TreeNode target;
    target.left=target.right=NULL;

    //leftMax和rightMin用来重构左右子树
    struct TreeNode *leftMax=&target;
    struct TreeNode *rightMin=&target;
    struct TreeNode *tmp=NULL;

    while(root!=NULL)
    {
        if(root->value<value)
        {
            //这种情况下不再需要进行splay
            if((tmp=root->right)==NULL)
                break;

            //这种情况需要旋转,和AVL中的"Right Right Case"旋转相同
            if(tmp->value<value)
            {
                root->right=tmp->left;
                tmp->left=root;
                root=tmp;
            }

            //旋转完后同样需要判断一下，这种情况不再需要splay
            if(root->right==NULL)
                break;

            //root节点比value小，把root节点记录到leftMax中
            leftMax->right=root;
            leftMax=root;
            //旋转后value依然比root节点的值大
            //      root                             node1
            //          \                            /   \
            //           node1      旋转==>        root  node3
            //           /   \                     /
            //        node2   node3              node2
            //
            root=root->right;

        }else if(root->value>value)
        {
            if((tmp=root->left)==NULL)
                break;

            //这种情况同样需要旋转，与AVL中的"Left Left Case"旋转相同
            if(tmp!=NULL && tmp->value>value)
            {
                root->left=tmp->right;
                tmp->right=root;
                root=tmp;
            }

            if(root->left==NULL)
                break;

            //root节点比value大，记录到rightMin中
            rightMin->left=root;
            rightMin=root;
            //旋转后的value比root节点的值小
            //         root                       node1
            //         /                          /    \
            //     node1            旋转==>   node2    root  
            //     /   \                                 \
            //  node2 node3                             node3
            root=root->left;
        }
        //找到节点
        else
        {
            //切换当前节点的左右子树的关联，把左子树保存到leftMax中
            //右子树保存到rightMax中
            leftMax->right=root->left;
            rightMin->left=root->right;
            break;
        }
    }

    //连接左右子树，此时整个树的重构完成
    //由于前面判断root->left==NULL和root->right==NULL的情况时，直接break出来，
    //所以这里不存在root==NULL的问题
    root->left=target.right;
    root->right=target.left;

    return root;
}


struct TreeNode *Insert(int value, struct TreeNode *root, bool& is_taller)
{
    //当前是空节点，此时需要创建一个
    if(root==NULL)
    {
        root=(struct TreeNode *)malloc(sizeof(struct TreeNode));
        root->balance=0;
        root->left=root->right=NULL;
        root->value=value;
        is_taller=true;

        return root;
    }

    //处理左子树的情况
    if(value < root->value)
    {
        //递归处理
        root->left=Insert(value,root->left,is_taller);

        //左右子树不平衡，需要进行平衡处理
        if(is_taller)
        {
            switch(root->balance)
            {
                //当前是平衡状态，则在左子树插入一个新节点后，偏向左边
                case 0:
                    root->balance=-1;
                    break;

                    //当前是右子树大，则现在为平衡状态
                case 1:
                    root->balance=0;
                    break;

                    //当前是左子树大，则需要对左子树进行调整
                case -1:
                    root=Rotate(root,root->left);
                    is_taller=false;
                    break;
            }
        }
        return root;
    }
    else if (value > root->value)
    {
        //在右子树插入新节点
        root->right=Insert(value,root->right,is_taller);
        //新节点需要进行调整
        if(is_taller)
        {
            switch(root->balance)
            {
                //当前平衡，现在偏向右边
                case 0:
                    root->balance=1;
                    break;

                    //当前右子树大，则插入后需要调整右子树
                case 1:
                    root=Rotate(root,root->right);
                    is_taller=false;
                    break;

                case -1:
                    root->balance=0;
                    break;
            }
        }
        return root;
    }
}

struct TreeNode *Rotate(struct TreeNode *root, struct TreeNode *child)
{
    if(root->balance==0)
    {
        return root;
    }

    //root的左子树大
    if(root->balance==-1)
    {
        //这种情况是图中的"Left Left Case"
        if(child->balance==-1)
        {
            //调整完后root和child都达到平衡状态
            root->balance=child->balance=0;
            return TurnRight(root,child);
        }
        //这种情况是图中的"Left Right Case"
        //要先处理这种结构为"Left Left Case“后，再进行旋转
        else if (child->balance==1)
        {
            root->balance=child->balance=0;

            child=TurnLeft(child,child->right);
            return TurnRight(root,child);
        }
    }
    //root的右子树大
    else if (root->balance==1)
    {
        //这种情况是"Right Left Case"
        //需要先处理成"Right Right Case"后再旋转
        if(child->balance==-1)
        {
            child->balance=root->balance=0;

            child=TurnRight(child,child->left);
            return TurnLeft(root,child);
        }
        //这种情况是"Right Right Case"
        else if(child->balance==1)
        {
            child->balance=root->balance=0;
            return TurnLeft(root,child);
        }
    }
    //这时child->balance==0
    return root;
}

//TurnLeft可以直接处理"Right Right Case",使它得到平衡
struct TreeNode * TurnLeft(struct TreeNode *root, struct TreeNode *child)
{
    root->right=child->left;
    child->left=root;
    return child;
}

//TurnRight可以直接处理"Left Left Case"
struct TreeNode * TurnRight(struct TreeNode *root, struct TreeNode *child)
{
    root->left=child->right;
    child->right=root;
    return child;
}

/*
//获取树的深度
int Depth(struct TreeNode *root)
{
    if(root==NULL)
        return 0;
    int leftDep=Depth(root->left);
    int rightDep=Depth(root->right);

    return (leftDep>rightDep?leftDep:rightDep)+1;
}
//
//这个Display函数用来打印树的结构，方便学习AVL、Splay等Tree
//
//如果有这样的树结构:
//             8
//       5           12
//   3      7     10     13
//
//则可以看成下面的样子
//|<-----a---->8
//|<--b->5<----a---->12
//   3      7     10     13
//
//第一层离屏幕左边的距离为a
//第二层离屏幕左边的距离为a/2=b,但是第二层中每一个节点之间的距离是a,这样刚好形成一个交错
//以此类推
//
void Display(const string& msg, struct TreeNode * root)
{

    //如果一个节点是NULL,则用这个来做占位
    struct TreeNode  Place;
    struct TreeNode * PlaceHolder=&Place; 

    //表示当前层的节点
    vector<struct TreeNode *> curLayer;
    //表示下一层的节点
    vector<struct TreeNode *> nextLayer;

    //取得树的深度
    int treeDepth=Depth(root);

    //输出缓冲区
    char output[treeDepth][240];
    memset(output,' ',treeDepth*240);
    //设置字符串结束符
    for(int i=0; i<treeDepth; ++i)
        output[i][239]=0;

    bool flag=true;
    //初始工作
    curLayer.push_back(root);

    //当前节点用到的宽度
    int curWidth=32;
    //父节点用到的宽度
    int parentWidth=curWidth;
    //记录当前打印的第N层
    int layer=0;
    while(flag)
    {

        //表示当前节点是这一层Layer中首个被打印的节点
        bool first=true;
        //当前被打印节点在output中的位置
        int pos=0;

        //下面对curLayer进行遍历，对curLayer中的节点取得其左右子树保存到
        //nextLayer中
        for(int i=0; i<curLayer.size(); ++i)
        {
            struct TreeNode *tmp=curLayer[i];
            //curLayer中当前节点不为NULl
            if(tmp!=NULL && tmp!=PlaceHolder)
            {
                if(first)
                {
                    first=false;
                    //当前是第一个打印节点，也是当前层的第一个节点
                    if(i==0)
                        pos=curWidth;
                    //当前是第一个打印节点，但不是当前层的第一个节点,这里的currentWidth相当于第一个节
                    //点距离屏幕最左边的偏移，而没有加上currentWidth之前的pos则是该节点在当前层中的相对
                    //偏移位置
                    //
                    //|<------ curWidth ------> |<-------------------------pos节点偏移---------------------->|
                    //|<---离屏幕左边的偏移---> XX <---节点偏移---> XX <---节点偏移---> XX <---节点偏移---> XX
                    else
                        pos=pos+curWidth;
                }

                //下面根据这个偏移在output输出缓冲区中打印相应的值
                int len=sprintf(&output[layer][pos],"%d",tmp->value);
                //这一步消除掉由sprintf打印时加的\0结束字符
                if(len>0)
                    output[layer][pos+len]=' ';
 
                //保存得到下一层的节点数据
                nextLayer.push_back(tmp->left);
                nextLayer.push_back(tmp->right);

            //这种情况需要用PlaceHolder来占一个位子
            }else if(tmp==NULL)
            {
                nextLayer.push_back(PlaceHolder);
                nextLayer.push_back(PlaceHolder);
            }

            //调整下一个节点输出的偏移
            pos+=parentWidth;
        }

        //计算下一层节点与当前节点的偏移
        parentWidth=curWidth;
        curWidth/=2;

        //下面做个检查，如果nextLayer中所有元素都是PlaceHolder，则此nextLayer就不
        //用处理了
        flag=false;
        for(int i=0; i<nextLayer.size(); ++i)
        {
            if(nextLayer[i]!=PlaceHolder && nextLayer[i]!=NULL)
            {
                flag=true;
                //交换nextLayer中的数据到curLayer中
                curLayer.swap(nextLayer);
                nextLayer.clear();
                break;
            }
        }
        ++layer;
    }

    //输出处理完后的内容
    cout<<msg<<endl;
    for(int i=0; i<treeDepth; ++i)
    {
        cout<<&output[i][0]<<endl;
    }
    cout<<endl;
}

*/
